package com.cskaoyan.recursion;


/*
        4.有一对兔子，从出生后第三个月开始每月生一对兔子，小兔子从第三个月开始每月也生一对兔子，
          假如是不死神兔，那么第20个月一共生多少对兔子？

          月份    1     2     3      4   ...
          数量    1     1     2      3   ...

        i, i + 1， i + 2 代表任意连续的3个月份
      N(i)     表示第i个月出生的兔子数量
      N(i - 1) 表示第i - 1个月出生的兔子数量
      N(i - 2) 表示第 i - 2个月及之前出生的兔子数量

      i                       i + 1                         i + 2
      N(i)     +              N(i)                          N(i) * 2
      N(i - 1) +              N(i - 1) + N(i - 1)           N(i - 1) * 2 + N(i - 1)
      N(i - 2) +              N(i - 2) + N(i - 2)           N(i - 2) * 2 + N(i - 2)

	  简单的观察一下
	  N(i)     +    N(i)               = 2N(i) = N(i) * 2
	  N(i - 1) +  N(i - 1) + N(i - 1)  = 3N(i - 1) =  N(i - 1) * 2 + N(i - 1)
	  N(i - 2) +  N(i - 2) +  N(i - 2) = 3N(i - 2) = N(i - 2) * 2 + N(i - 2)
	  i月的数量   i+1月兔子数量                      i+2月兔子的数量

	  f(n)表示第n个月兔子的数量,
	  f(n) = f(n - 1) + f(n - 2)
	  f(1) = 1
	  f(2) = 1

	  实际上, 斐波那契数列的递推公式
	  f(n) =  f(n - 1) + f(n - 2)
	  f(1) = 1
	  f(2) = 1

	  递归的缺陷:

 */
public class Demo5Exercise {


    public static void main(String[] args) {

        int month = 20;
        long result = countRabbit(month);
        System.out.println(result); //6765

        int n = 20;
        long fibonacci = fibonacci(n);
        System.out.println(fibonacci);

        long f = f(n);
        System.out.println(f);

    }

    /*
         不死神兔
     */
    public static long countRabbit(int month) {
        if (month == 1 || month == 2) {
            return 1;
        }
        return countRabbit(month - 1) + countRabbit(month - 2);
    }

    /*
          n 项数
     */
    public static long fibonacci(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }

        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    /*
         使用循环的方式计算斐波那契数列第n项的值
     */

    public static long f(int n) {
        /*
              辅助数组(从1开始使用)，第i个位置的值,存
              斐波那契数列第i项的值
          */
        int[] tmp = new int[n + 1];
        tmp[1] = 1;
        tmp[2] = 1;
        for (int i = 3; i<= n; i++) {
            tmp[i] = tmp[i - 1] + tmp[i - 2];
        }
        return tmp[n];
    }


}
